#include <bits/stdc++.h>

using namespace std;

// 编辑距离
// 给你两个单词 word1 和 word2
// 请返回将 word1 转换成 word2 所使用的最少代价
// 你可以对一个单词进行如下三种操作：
// 插入一个字符，代价a
// 删除一个字符，代价b
// 替换一个字符，代价c
// 测试链接 : https://leetcode.cn/problems/edit-distance/

class Solution 
{
private:
    // 原初尝试版
	// a : str1中插入1个字符的代价
	// b : str1中删除1个字符的代价
	// c : str1中改变1个字符的代价
	// 返回从str1转化成str2的最低代价
    int editDistance1(string& word1, string& word2, int a, int b, int c)
    {
        // dp[i][j] : s1[前缀长度为i]想变成s2[前缀长度为j]，至少付出多少代价
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 0; i <= m; ++i) dp[i][0] = i * b; // 删除字符
        for(int j = 1; j <= n; ++j) dp[0][j] = j * a; // 插入字符
        
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                // dp[i][j - 1] + a : 插入一个字符 word2[j - 1]
                // dp[i - 1][j] + b : 删除一个字符 word1[i - 1]
                dp[i][j] = min(dp[i][j - 1] + a, dp[i - 1][j] + b);
                if(word1[i - 1] == word2[j - 1]) // 字符相等不需要进行替换
                {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                }
                else // 字符不相等需要进行替换
                {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + c);
                }
            }
        }

        return dp[m][n];
    }

    // 空间压缩
    // a : str1中插入1个字符的代价
	// b : str1中删除1个字符的代价
	// c : str1中改变1个字符的代价
	// 返回从str1转化成str2的最低代价
    int editDistance2(string& word1, string& word2, int a, int b, int c)
    {
        int m = word1.size(), n = word2.size();
        vector<int> dp(n + 1);
        for(int j = 1; j <= n; ++j) dp[j] = j * a; // 插入字符

        for(int i = 1, leftUp, backUp; i <= m; ++i)
        {
            leftUp = (i - 1) * b;
            dp[0] = i * b;
            for(int j = 1; j <= n; ++j)
            {
                backUp = dp[j]; // 此时的 dp[j] 是上一行的值
                if(word1[i - 1] == word2[j - 1])
                {
                    dp[j] = leftUp;
                }
                else
                {
                    dp[j] = min(min(dp[j] + b, dp[j - 1] + a), leftUp + c);
                }
                leftUp = backUp; // j++ 后，上一行的 dp[j] 就变成了左上角的值
            }
        }

        return dp[n];
    }

public:
    // 已经展示太多次从递归到动态规划了
	// 直接写动态规划吧
    int minDistance(string word1, string word2) 
    {
        return editDistance1(word1, word2, 1, 1, 1);
    }
};